# https://gitee.com/shnlb2006/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%AF%A6%E8%A7%A3%E8%BF%9B%E9%98%B6.md

# 暴力递归  空间o(1) 时间o(2^n)
# 子问题个数x子问题时间复杂度=2^n个子问题(二叉树节点数量)*o(1)(一行函数) = o(2^n)
def fib(num):
    if num < 1:
        return 0
    if num == 1 or num == 2:
        return 1
    return fib(num - 1) + fib(num - 2)


# 备忘录递归解决解决重叠子问题，自顶向下 f(20)->f(19)->....   o(n)个子问题*o(1)计算 时间复杂度= o(n),空间o(n)
def fib_note(num):
    if num < 1:
        return 0
    fib_map = {}
    return fib_note_help(fib_map, num)


def fib_note_help(fib_map, num):
    if num == 1 or num == 2:
        return 1
    if fib_map.__contains__(num):
        return fib_map[num]
    fib_map[num] = fib_note_help(fib_map, num - 1) + fib_note_help(fib_map, num - 2)
    return fib_map[num]


# 动态规划迭代解决问题，自下而上，和递归的区别是找到状态与状态之间的关联性
# 动态规划一般脱离递归，通过迭代解决,空间占用o(n)，时间复杂度o(n)
def fib_dynamic(num):
    if num < 1:
        return 0
    fib_map = {1: 1, 2: 1}
    for value in range(3, num + 1):
        fib_map[value] = fib_map[value - 1] + fib_map[value - 2]
    return fib_map[num]


# 进一步降低空间占用，实际上后一个数字只与前两个数字有关系，和其他没关系，空间占用可以降低到o(2) 时间复杂度o(n)
def fib_dynamic_update(num):
    if num < 1:
        return 0
    prev = curr = 1
    for value in range(3, num + 1):
        sum = curr + prev
        prev = curr
        curr = sum
    return curr


if __name__ == '__main__':
    for a in range(10):
        print(fib(a) == fib_note(a) == fib_dynamic(a) == fib_dynamic_update(a))
        print(fib_dynamic_update(a))
